Nächste Woche gibt es keine Aufnahme. Wer wissen will, was läuft, muss kommen.

Dankeschön.

So.

Ja, machen wir uns noch mal kurz klar, wo wir sind. Wir hatten uns angesehen parametrische

Datentypen, die entstehen dadurch, dass wir binäre Funktoren, also Bi-Funktoren, uns

ansehen zur Beschreibung der Syntax praktisch, also der Konstruktoren, die hier im zweiten

Argument einen Parameter haben. Achtung, wer einen Blick wirft in Algebra of Programming,

also das Buch wird feststellen, dass da die Parameterkategorie das erste Argument ist.

Das hatte ich nicht rechtzeitig gemerkt. Das hat wohl Stefan irgendwie aus irgendeinem

Grund so rumgemacht. Das würde ich wohl nächstes Mal dann umdrehen wollen, aber jetzt ist es

zu spät. So. Und wir definieren für ein A-Objekt,

das ist ein Funktor, der auf Objekten initiale Algebren nimmt für den Funktor, der entsteht,

wenn wir hier das zweite Argument festhalten. Das heißt, i von a ist die initiale f von

unterstrich Komma a-Algebra, also die initiale Algebra des Funktors, der entsteht, wenn

wir das zweite Argument hier auf a fixieren. Genauer gesagt ist das hier nur das unterliegende

Objekt der initialen Algebra und die Strukturabbildung schreiben wir iota. Genauer gesagt iota a.

So. Und wir hatten uns verschiedene Beispiele angesehen, also die üblichen parametrisierten

Datentypen, die man so kennt, also Bäumelisten und so weiter, mit einem Parameter, der eben

sagt, welche Einträge da so an den Blättern oder in der Liste drinstehen. Das sind alles

verschiedene Datentypen in diesem Sinne. Wir haben uns klar gemacht, dass dieses Ding

hier tatsächlich ein Funktor ist. Und wir hatten gezeigt folgendes Gesetz. Und wie

hieß es jetzt? Also, wenn ich mir eine Banane nehme, also Banane von a, also den eindeutigen

Homomorphismus aus der initialen Algebra in eine Algebra a und das komponiere mit dem

Typfunktor angewendet auf irgendeine Abbildung oder einen Morphismus, also man denke hier

an sowas wie List von p oder Tree von p, sprich also einfach ein Map, wenn man so will,

das also über Datenstrukturen rüberrödelt und auf alle Einträge p anwendet, dann können

wir das hier, was ja im Endeffekt eine Verkettung von zwei Schleifen ist, eine, die über die

Datenstruktur rüberrödelt und überall p anwendet und eine, die anschließend die rekursive

Definition von dem a aus, also von dem Banane a ausführt, das können wir mehr oder weniger

in einen Durchlauf fusionieren, deswegen heißt das Typfunktorfusion. Da kommt also gerade

raus, das kommt raus, Banane von a komponiert mit f von int,p. So, das hatten wir letztes

Mal gezeigt, nützliches Gesetz. So, und wir wollen jetzt einmal einsteigen in so eine

nette kleine Anwendung, die in dem Bereich stattfindet, und zwar gucken wir uns an das

Horner Schema. So, wer, ich weiß nicht, wie sind die Schulen heutzutage noch so drauf,

wer weiß denn, was das Horner Schema ist, war eine Zeit lang typischer Schulstoff.

Ja, ungefähr, also, achso, sogar universitär, ja, gut. Ja, also das Horner Schema ist so

etwas aus der Zeit, wo Multiplikationen noch so richtig was gekostet haben. So, nehmen wir

uns mal ein Polynom, also das besteht aus irgendwelchen Monomen, die bestehen jeweils

aus koeffizient mal potenz der Variablen. Also ich fange an mit a n mal x hoch n plus

hier und so weiter, dann kommt am Ende plus a 1 x ergänze x hoch 1, nicht plus a 0 ergänze

x hoch 0. So, das ist so ein Polynom. Ich das so stehen lasse, wie viele Multiplikationen

brauche ich, um das auszuwerten? Geschätzt? Oder genau? Ne, es kommt auf die Faktoren nicht

an. Also das ist jetzt nicht, ich habe nicht gefragt, wie lange es dauert, sondern nur

wie viele Multiplikationen ich brauche. Also, 200-stellige Zahlen multiplizieren dauert

genauso lange wie dreimal fünf Rechnen. Also das ist nicht realistisch, aber typische

Abstraktion. N Quadrat so ungefähr, also sagen wir mal o von n Quadrat. Stimmt das? Ja. Also

ganz genau rechnen, hier haben wir eine Multiplikation, zwei Multiplikation, drei Multiplikation,

hier ist n plus eins, ja, also Summe i gleich eins bis n plus eins über i ist gleich nach

kleinem Gauss, konzentrieren, was ist das? N plus eins mal n plus zwei, glaube ich halbe

kann das sein, ne? So, also, gut, rechnen wir nicht aus, was das genau ist. Gut, wirklich